<?php

class Tree implements Iterator,Countable
{
    const ID = 'id';
    const PID = 'pid';
	const LEVEL ='level';
    const DATA = 'data';
    const CHILDREN = 'child';
	const DFS = 'DFS';
	const BFS = 'BFS';
	const PARENT='pid';
    protected $_tree = array();
    protected $_filename = '';
    protected $_prefix = 'tree_';
    protected $_path = '';
    protected $_rootid = 0;
	protected $_lastid = 0;
	protected $_way = self::DFS;
	protected $_stack = array();
	
    public function __construct($name, $path = '')
    {
        $this->loadTree($name, $path);
    }
    public function loadTree ($name, $path = '')
    {
        if ($path != '') {
            if (is_dir($path)) {
                $this->_path = rtrim($path, '/\\') . DIRECTORY_SEPARATOR;
            } else {
                die('No such directory :' . $path);
            }
        }
        $name = md5($name);
        $this->_filename = $this->_path . $this->_prefix . $name ;
        if (is_file($this->_filename)) {
			$this->_tree = json_decode(file_get_contents($this->_filename),true);
            $this->_initTree();
            return true;
        }
        return false;
    }
    protected function _initTree ()
    {
		$ary = $this->listToTree($this->_tree);
		$this->_rootid = $ary['topid'];
		$this->_lastid = $ary['lastid'];
		$this->_tree[$this->_rootid][self::LEVEL] = 1;
        return $this;
    }
	
	public function listToTree(&$list){
		$return = array('topid'=>0,'lastid'=>0);
		foreach ($list as $id => &$node){
	            if (isset($list[$node[self::PID]]))
    	            $list[$node[self::PID]][self::CHILDREN][$id] = &$node;
        	    else
            	    $return['topid'] = $id;
				if ($id > $return['lastid']) $return['lastid'] = $id;
			}
        return $return;
	}
	
    public function setTreeByList (array $list)
    {
        if (!$this->_checkList($list)){
            die('Incorrect data format');
        }
        $this->_tree = $list;
        $this->_initTree();
        return true;            
    }
    
    public function getTree($id = null)
    {
		if (null === $id) $id = $this->_rootid;
        if (isset($this->_tree[$id]))
            return $this->_tree[$id];
        else
            return null;

    }
	
	public function getParent($id){
		if (isset($this->_tree[$id]) && isset($this->_tree[$this->_tree[$id][self::PID]])){
			return $this->_tree[$this->_tree[$id][self::PID]];
		}
		return null;
	}
       
    public function getParentsId($start,$level = null)
    {   
        
        $parent = array();
        $id = $start;
        do{
            if (!isset($this->_tree[$id])) break;
            $pid = $this->_tree[$id][self::PID];
            if (null !== $level && !$level--) break;
            if (!isset($this->_tree[$pid])) break;
        }
        while(true);
        return $parent;
    }
	
	public function getChildren($id){
		if (isset($this->_tree[$id])){
			return $this->_tree[$id][self::CHILDREN];
		}
		return null;
	}
	
    public function getTreeAll()
	{
		return $this->_tree;
	}
	
    public function getTreeList()
    {
		if (isset($this->_tree)) {
			return $this->toList($this->_tree);
		}
		return null;
    }
	
	public function toList($tree){
		$ary = array();
		foreach ($tree as $id => $node){
			unset($node[self::CHILDREN]);
			$ary[$id] = $node;
		}
		return $ary;
	}
	
	public function getDepth(){
		$depth = 1;
		$id = $this->_rootid;
		$stack = array($id);
		$i = 0;
		if (!isset($this->_tree[$id][self::LEVEL]))
			$this->_tree[$id][self::LEVEL] = 1;
		do{
			$id = $stack[$i++];
		   $pid = $this->_tree[$id][self::PID];
           if (isset($this->_tree[$id][self::CHILDREN])){
               $stack = array_merge($stack,array_keys($this->_tree[$id][self::CHILDREN]));   
           }
		   if (isset($this->_tree[$id][self::LEVEL])){
		   		$level = $this->_tree[$id][self::LEVEL];
		   }
		   else {
		   		$level = $this->_tree[$pid][self::LEVEL] + 1;
		   		$this->_tree[$id][self::LEVEL] = $level;
		   }
		   if ($depth < $level) $depth = $level;
		}while(isset($stack[$i]));
		return $depth;
	}
	
    public function getLastId(){
        return $this->_lastid;
    }
	
	public function getRootId(){
		return $this->_rootid;
	}
	
	public function getRoot(){
		return $this->_tree[$this->_rootid];
	}
			
	public function getData($id){
		if (isset($this->_tree[$id])){
			return $this->_tree[$id][self::DATA];
		}
		return null;
	}
	
	public function setData($id,$data){
		if (isset($this->_tree[$id])){
			$this->_tree[$id][self::DATA] = $data;
			return true;
		}
		return false;
	}
    	
    public function addRoot($data = null)
    {
        $root = array(
            self::ID => $this->_rootid, 
            self::PID => $this->_rootid - 1, 
			self::LEVEL => 1,
            self::DATA => $data
        );  
        $this->_tree[$this->_rootid] = &$root;
		$this->_lastid = $this->_rootid;
        return $this->_rootid;
    }
       
    public function addLeaf($flid,$pid,$data = null)
    {
        if (!isset($this->_tree[$pid])){
            if (isset($this->_tree[$this->_rootid]))
                $pid = $this->_rootid;
            else {
                $this->_lastid = $this->addRoot($data); 
				return $this->_lastid;
			}
        }
		//$id = ++$this->_lastid;
		$id = $flid;
		$level = isset($this->_tree[$pid][self::LEVEL])? $this->_tree[$pid][self::LEVEL] + 1 : null;
        $this->_tree[$id] = array(
            self::ID => $id, 
            self::PID => $pid, 
			self::LEVEL => $level,
            self::DATA => $data
        );
        $this->_tree[$pid][self::CHILDREN][$id] = &$this->_tree[$id];
        return $id;
    }
	public function insertChild($pid, $children)
	{
		if (!isset($this->_tree[$pid])){
			return false;
		}
		if ($children instanceof self){
			$children = $children->getTree();
		}
		
		if (is_array($children)){
			$children = $this->toList($children);
			$lastid = $this->_lastid + 1;
			$list = array();
			foreach ($children as $id => $node){
				$node[self::ID] +=$lastid;
				$node[self::PID] +=$lastid;
				$list[$id + $lastid] = $node;
			}
			$ary = $this->listToTree($list);
			$this->_lastid = $ary['lastid'];
			$list[$ary['topid']][self::PID] = $pid;
			$this->_tree += $list;
			$this->_tree[$pid][self::CHILDREN][$ary['topid']] = &$this->_tree[$ary['topid']];
			return $this->_lastid;
		}
		return $this->addLeaf($pid,$children);
	}
	
    public function deleteChild($id){
        if (!isset($this->_tree[$id])){
            return null;
        }
		$pid = $this->_tree[$id][self::PID];
		$delTree = array();
		if (isset($this->_tree[$pid])){
			unset($this->_tree[$pid][self::CHILDREN][$id]);
		}
		$stack = array($id);
		do{
			$id = array_pop($stack);
			if (isset($this->_tree[$id][self::CHILDREN]))
				$stack =array_merge($stack, array_keys($this->_tree[$id][self::CHILDREN]));
			$delTree[$id] = $this->_tree[$id];
			unset($this->_tree[$id]);
		}while(!empty($stack));
        return $delTree;
    }
    
    public function emptyTree(){
        $this->_tree = array();
		$this->_rootid = 0;
		$this->_lastid = 0;
        return true;
    }
    
    public function destroyTree(){
        $this->emptyTree();
        if (is_file($this->_filename))
            unlink($this->_filename);
        return true;            
    }
    
    protected function _checkList (array $list)
    {
        $isChecked = true;
		$topNum = 0;
        foreach ($list as $id => $node) {
            if (! isset($node[self::ID]) || ! isset($node[self::PID]) || $node[self::ID] != $id) {
                $isChecked = false;
                break;
            }else{
				if (!isset($list[$node[self::PID]])) $topNum++;
				if ($topNum > 1){
					$isChecked = false;
	                break;
				}
			}
        }
        return $isChecked;
    }
	
	public function getLevel($id){
		if (isset($this->_tree[$id]) && isset($this->_tree[$id][self::LEVEL]) )
			return $this->_tree[$id][self::LEVEL];
		$level = 0;
		$id2 = $id;
		while(isset($this->_tree[$id2])){
			if (isset($this->_tree[$id2][self::LEVEL])){
				$level += $this->_tree[$id2][self::LEVEL];
				break;
			}
			$level++;
			$id2 = $this->_tree[$id2][self::PID];
		}
		if (isset($this->_tree[$id]))
			$this->_tree[$id][self::LEVEL] = $level;
		return $level;
	}
       
    public function DFS($callback = null,$id = null){
        if (null === $id) $id = $this->_rootid;
        if (!isset($this->_tree[$id])){
            return null;
        }
        if (null == $callback ){
            return null;
        }
        $stack = array($id);
		$return = null;
        do{
		   $id = array_shift($stack);
		   $children = null;
           if (isset($this->_tree[$id][self::CHILDREN])){
			   $children = array_keys($this->_tree[$id][self::CHILDREN]);
			   $stack = array_merge($children,$stack);
           }
		   $args = array(
		   		self::ID => $id,
				self::PID => $this->_tree[$id][self::PID],
				self::DATA => &$this->_tree[$id][self::DATA],
				self::LEVEL => $this->getLevel($id),
				self::CHILDREN => $children
		   );

		   $back = call_user_func($callback,$args);
		   if (isset($back)){
			   if (is_string($back)) $return .= $back;
			   else if (is_array($back)) $return[] = $back;
			   else if (is_int($back)) $return += $back;
			   else if (is_bool($back) && $back) $return = $this->_tree[$id];
		   }
		}while(!empty($stack));
        return $return;
        
    }
    
    public function BFS($callback = null,$id = null){
        if (null === $id) $id = $this->_rootid;
        if (!isset($this->_tree[$id])){
            return array();
        }
        if (null == $callback ){
            $callback = null;
        }
        $stack = array($id);
		$return = null;
        do{
			$id = array_shift($stack);
			$children = null;
            if (isset($this->_tree[$id][self::CHILDREN])){
				$children = array_keys($this->_tree[$id][self::CHILDREN]);
                $stack = array_merge($stack,$children);   
            }   
		    $args = array(
		   		self::ID => $id,
				self::PID => $this->_tree[$id][self::PID],
				self::DATA => &$this->_tree[$id][self::DATA],
				self::LEVEL => $this->getLevel($id),
				self::CHILDREN => $children
		   );

			$return = call_user_func($callback,$args);
			if (isset($back)){
			   if (is_string($back)) $return .= $back;
			   else if (is_array($back)) $return[] = $back;
			   else if (is_int($back)) $return += $back;
			   else if (is_bool($back) && $back) $return = $this->_tree[$id];
		   }

        }while(!empty($stack));
        return $return;
    }
    
    public function saveTree(){
		file_put_contents($this->_filename, json_encode($this->toList($this->_tree)));
        return true;
    }    
	public function setWay($way = self::DFS){
		if (in_array($way,array(self::DFS,self::BFS))){
			$this->_way = $way;
			$this->rewind();
		}
		return $this;
	}
	
	public function rewind()
	{
		if (isset($this->_tree[$this->_rootid]))
		{
			$this->_stack = array($this->_rootid);
		}
		else{
			$this->_stack = array();
			
		}
        return $this;
	}
	
	public function next()
	{
		$id = array_shift($this->_stack);
		if (isset($this->_tree[$id][self::CHILDREN])){
		   $children = array_keys($this->_tree[$id][self::CHILDREN]);
		   if ($this->_way == self::BFS)
			   $this->_stack = array_merge($this->_stack,$children);
		   else
			   $this->_stack = array_merge($children,$this->_stack);
	    }
	}
	
	public function count()
	{
		return count($this->_tree);
	}
	
	public function key()
	{
		return current($this->_stack);
	}
	
	public function current()
	{
		$id = current($this->_stack);
		if (isset($this->_tree[$id])){
			return $this->_tree[$id];
		}
		else
			return null;
	}
	
	public function valid()
	{
		return !empty($this->_stack);
	}
}

